package com.company.笔试.求两个有序数组中位数;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 获取两个有序数组的中位数，两个数组同为增序数组，数组类型都为Int型。
假设两个数组的元素总个数为N，返回N/2
     * @param arr1 int整型一维数组 第一个有序数据组
     * @param arr2 int整型一维数组 第二个有序数据组
     * @return int整型
     */
    public int getMedia (int[] arr1, int[] arr2) {
        // write code here
        int l = (arr1.length+arr2.length+1)/2;
        int r = (arr1.length+arr2.length+2)/2;
        return (mid(arr1,0,arr1.length-1,arr2,0,arr2.length-1,l)+mid(arr1,0,arr1.length-1,arr2,0,arr2.length-1,r))/2;
        
    }

    public static int mid(int[] arr1, int start1,int end1,int[] arr2, int start2,int end2,int m) {
        int length1 = end1-start1+1;
        int length2 = end2-start2+1;
        if (length1>length2) return mid(arr2,start2,end2,arr1,start1,end1,m);
        if (length1==0)return arr2[start2+m-1];
        if (m==1)return Math.min(arr1[start1],arr2[start2]);
        int index1 = start1 + Math.min(length1,m/2)-1;
        int index2 = start2 + Math.min(length2,m/2)-1;
        if (arr1[index1]>arr2[index2]){
            return  mid(arr1,start1,end1,arr2,index2+1,end2,m-(index2-start2+1));
        }else {
            return  mid(arr1,index1+1,end1,arr2,start2,end2,m-(index1-start1+1));
        }

    }

}